package leetcode.onehundred;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//234. 回文链表
public class IsPalindrome {
    //1.使用栈
    public boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        temp = head;
        for (int i = 0; i < stack.size(); i++) {
            Integer l1 = stack.pop();
            if (l1 != temp.val) {
                return false;
            }
            temp = temp.next;
        }
        return true;
    }

    //2.使用数组---将数据放到数组里，通过数组判断回文
    public boolean isPalindrome2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        //双指针判断是否是回文
        int p = 0;
        int q = list.size() - 1;
        while (p < q) {
            if (!list.get(p).equals(list.get(q))) {
                return false;
            }
            p++;
            q--;
        }
        return true;
    }

    //3.快慢指针----快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。
    // 当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

    //算法步骤：
    //找到前半部分链表的尾节点。
    //反转后半部分链表。
    //判断是否回文。
    //恢复链表。
    //返回结果。

    public boolean isPalindrome3(ListNode head) {
        if (head == null) {
            return true;
        }

        //1.利用快慢指针找到前部分的尾部（后部分的头部）
        ListNode firstEnd = slowAndFast(head);
        //2.反转后半部分的链表
        ListNode secondStart = reverseList(firstEnd.next);
        //3.判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondStart;

        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    //反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

    private ListNode slowAndFast(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
